{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import iplantuml"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. 数学模型\n",
    "\n",
    "方程 $f(x)$ 在 $x_k$ 处的切线方程\n",
    "$$\n",
    "y = f(x_k) + f'(x_k)(x_{k+1}-x_k) \\tag 1\n",
    "$$\n",
    "令与 $x$ 轴交点为 $x_{k+1}$, 则\n",
    "\n",
    "$$\n",
    "x_{k+1} = x_k - \\frac{f(x_k)}{f'(x_k)} \\tag 2\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. 算法设计"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing output for /home/jack/Desktop/structures-algorithms/faafe529-1231-4453-bbad-98bfe8e5c9c3.uml to faafe529-1231-4453-bbad-98bfe8e5c9c3.svg\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" contentStyleType=\"text/css\" height=\"415px\" preserveAspectRatio=\"none\" style=\"width:198px;height:415px;background:#FFFFFF;\" version=\"1.1\" viewBox=\"0 0 198 415\" width=\"198px\" zoomAndPan=\"magnify\"><defs/><g><ellipse cx=\"90.1226\" cy=\"20\" fill=\"#222222\" rx=\"10\" ry=\"10\" style=\"stroke:#222222;stroke-width:1.0;\"/><rect fill=\"#F1F1F1\" height=\"36.9688\" rx=\"12.5\" ry=\"12.5\" style=\"stroke:#181818;stroke-width:0.5;\" width=\"138.5341\" x=\"20.8555\" y=\"50\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"70.9165\" x=\"30.8555\" y=\"71.1387\">提供初始值 x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"18.479\" x=\"101.772\" y=\"74.8462\">k+1</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"29.1387\" x=\"120.251\" y=\"71.1387\">=1.5</text><rect fill=\"#F1F1F1\" height=\"36.9688\" rx=\"12.5\" ry=\"12.5\" style=\"stroke:#181818;stroke-width:0.5;\" width=\"67.9487\" x=\"56.1482\" y=\"150.9688\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"7.1016\" x=\"66.1482\" y=\"172.1074\">x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"5.2119\" x=\"73.2498\" y=\"175.8149\">k</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"17.1563\" x=\"78.4617\" y=\"172.1074\">=x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"18.479\" x=\"95.6179\" y=\"175.8149\">k+1</text><rect fill=\"#F1F1F1\" height=\"36.9688\" rx=\"12.5\" ry=\"12.5\" style=\"stroke:#181818;stroke-width:0.5;\" width=\"135.7417\" x=\"22.2517\" y=\"215.4375\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"7.1016\" x=\"32.2517\" y=\"236.5762\">x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"18.479\" x=\"39.3533\" y=\"240.2837\">k+1</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"17.1563\" x=\"57.8323\" y=\"236.5762\">=x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"5.2119\" x=\"74.9885\" y=\"240.2837\">k</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"20.3379\" x=\"80.2004\" y=\"236.5762\">-f(x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"5.2119\" x=\"100.5383\" y=\"240.2837\">k</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"32.3496\" x=\"105.7502\" y=\"236.5762\">)/df(x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"9\" lengthAdjust=\"spacing\" textLength=\"5.2119\" x=\"138.0999\" y=\"240.2837\">k</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"4.6816\" x=\"143.3118\" y=\"236.5762\">)</text><polygon fill=\"#F1F1F1\" points=\"90.1226,106.9688,102.1226,118.9688,90.1226,130.9688,78.1226,118.9688,90.1226,106.9688\" style=\"stroke:#181818;stroke-width:0.5;\"/><polygon fill=\"#F1F1F1\" points=\"32,272.4063,148.2451,272.4063,160.2451,284.4063,148.2451,296.4063,32,296.4063,20,284.4063,32,272.4063\" style=\"stroke:#181818;stroke-width:0.5;\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"28.6226\" x=\"94.1226\" y=\"306.6167\">False</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"30.2554\" x=\"32\" y=\"286.7144\">abs(x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"8\" lengthAdjust=\"spacing\" textLength=\"16.4258\" x=\"62.2554\" y=\"289.7344\">k+1</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"10.479\" x=\"78.6812\" y=\"286.7144\">-x</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"8\" lengthAdjust=\"spacing\" textLength=\"4.6328\" x=\"89.1602\" y=\"289.7344\">k</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"54.4521\" x=\"93.793\" y=\"286.7144\">) &gt;= 1e-5</text><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"11\" lengthAdjust=\"spacing\" textLength=\"24.981\" x=\"160.2451\" y=\"281.812\">True</text><rect fill=\"#F1F1F1\" height=\"33.9688\" rx=\"12.5\" ry=\"12.5\" style=\"stroke:#181818;stroke-width:0.5;\" width=\"54.9162\" x=\"62.6645\" y=\"328.1167\"/><text fill=\"#000000\" font-family=\"sans-serif\" font-size=\"12\" lengthAdjust=\"spacing\" textLength=\"34.9162\" x=\"72.6645\" y=\"349.2554\">输出 x</text><ellipse cx=\"90.1226\" cy=\"393.0854\" fill=\"none\" rx=\"11\" ry=\"11\" style=\"stroke:#222222;stroke-width:1.0;\"/><ellipse cx=\"90.1226\" cy=\"393.0854\" fill=\"#222222\" rx=\"6\" ry=\"6\" style=\"stroke:#222222;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"30\" y2=\"50\"/><polygon fill=\"#181818\" points=\"86.1226,40,90.1226,50,94.1226,40,90.1226,44\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"187.9375\" y2=\"215.4375\"/><polygon fill=\"#181818\" points=\"86.1226,205.4375,90.1226,215.4375,94.1226,205.4375,90.1226,209.4375\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"130.9688\" y2=\"150.9688\"/><polygon fill=\"#181818\" points=\"86.1226,140.9688,90.1226,150.9688,94.1226,140.9688,90.1226,144.9688\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"160.2451\" x2=\"172.2451\" y1=\"284.4063\" y2=\"284.4063\"/><polygon fill=\"#181818\" points=\"168.2451,207.9375,172.2451,197.9375,176.2451,207.9375,172.2451,203.9375\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"172.2451\" x2=\"172.2451\" y1=\"118.9688\" y2=\"284.4063\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"172.2451\" x2=\"102.1226\" y1=\"118.9688\" y2=\"118.9688\"/><polygon fill=\"#181818\" points=\"112.1226,114.9688,102.1226,118.9688,112.1226,122.9688,108.1226,118.9688\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"252.4063\" y2=\"272.4063\"/><polygon fill=\"#181818\" points=\"86.1226,262.4063,90.1226,272.4063,94.1226,262.4063,90.1226,266.4063\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"86.9688\" y2=\"106.9688\"/><polygon fill=\"#181818\" points=\"86.1226,96.9688,90.1226,106.9688,94.1226,96.9688,90.1226,100.9688\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"296.4063\" y2=\"328.1167\"/><polygon fill=\"#181818\" points=\"86.1226,318.1167,90.1226,328.1167,94.1226,318.1167,90.1226,322.1167\" style=\"stroke:#181818;stroke-width:1.0;\"/><line style=\"stroke:#181818;stroke-width:1.0;\" x1=\"90.1226\" x2=\"90.1226\" y1=\"362.0854\" y2=\"382.0854\"/><polygon fill=\"#181818\" points=\"86.1226,372.0854,90.1226,382.0854,94.1226,372.0854,90.1226,376.0854\" style=\"stroke:#181818;stroke-width:1.0;\"/><!--SRC=[Aov9B2hXidhMF-79ljbFE-O-NTxzj66FGeLDSMcINRQseOq-Y65hg6TgpLMKMf2QMCAb00HMK0LGQJJbrYXgu8QWwD5Dqq3XQ-gde8l0R5GepyZCITL8J2hMG3DI5rM3WfsjWc6ghgbcPh56I55fgcPUVec6Ms9ESQecn4Klzar-shvBeSAQgxWalm00]--></g></svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%plantuml \n",
    "@startuml\n",
    "start\n",
    ":提供初始值 x<sub>k+1</sub>=1.5;\n",
    "repeat\n",
    "    :x<sub>k</sub>=x<sub>k+1</sub>;\n",
    "    :x<sub>k+1</sub>=x<sub>k</sub>-f(x<sub>k</sub>)/df(x<sub>k</sub>);\n",
    "repeat while(abs(x<sub>k+1</sub>-x<sub>k</sub>) >= 1e-5)is(True)not(False)\n",
    "    :输出 x;\n",
    "stop\n",
    "@enduml"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. 代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0000000000163607"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def solution(a, b, c, d):\n",
    "    def f(x):\n",
    "        return a*x**3 + b*x**2 + c*x + d \n",
    "    def df(x):\n",
    "        return 3*a*x**2 + 2*b*x + c \n",
    "    x1 = 1.5\n",
    "\n",
    "    x0 = x1\n",
    "    x1 = x0 - f(x0)/df(x0)\n",
    "\n",
    "    while(abs(x1-x0) >= 1e-5):\n",
    "        x0 = x1\n",
    "        x1 = x0 - f(x0)/df(x0)\n",
    "    return x1\n",
    "\n",
    "solution(2, -4, 3, -6)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
